package leetcode.code1157;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Random;

public class MajorityChecker {

	Map<Integer, List<Integer>> map;
	int[] arr;

	public MajorityChecker(int[] arr) {
		this.arr = arr;
		map = new HashMap<>();
		for (int i = 0; i < arr.length; i++) {
			int num = arr[i];
			map.computeIfAbsent(num, key -> new ArrayList<>()).add(i);
		}
	}

	public int query(int left, int right, int threshold) {
		for (int i = 0; i < 20; i++) {
			int width = right - left + 1;
			int index = randrange(left, right + 1);
			int num = this.arr[index];
			int size = f(map.get(num), left, right);
			if (size >= threshold) {
				return num;
			} else if (size * 2 == width) {
				return -1;
			}
		}
		return -1;
	}

	private int f(List<Integer> list, int left, int right) {
		int L = bisect_left(list, left);
		int R = bisect_right(list, right);
		return R - L;
	}

	private int bisect_right(List<Integer> list, int num) {
		int l = 0, r = list.size();
		while (l < r) {
			int m = (r - l) / 2 + l;
			if (list.get(m) > num) {
				r = m;
			} else {
				l = m + 1;
			}
		}
		return l;
	}

	private int bisect_left(List<Integer> list, int num) {
		int l = 0, r = list.size();
		while (l < r) {
			int m = (r - l) / 2 + l;
			if (list.get(m) >= num) {
				r = m;
			} else {
				l = m + 1;
			}
		}
		return l;
	}

	
	public int randrange(int start,int stop) {
		return (int) (Math.random() * (stop - start)) + start;
	}
	

}
